﻿#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)

// 遍历的方式
static int useLoop(const int* numbers, size_t size)
{
	unordered_map<int, vector<int>*> table;

	for (int i = 0; i < size; i++)
	{
		int cur = numbers[i];
		vector<int> *vec = new vector<int>();
		vec->push_back(cur);
		table.insert({ cur, vec });
		int left = i - 1;
		int right = i + 1;
		while (left >= 0)
		{
			if (numbers[left] < cur)
			{
				break;
			}
			else
			{
				vec->push_back(numbers[left]);
				--left;
			}
		}

		while (right < size)
		{
			if (numbers[right] < cur)
			{
				break;
			}
			else
			{
				vec->push_back(numbers[right]);
				++right;
			}
		}
	}

	int max = 0;

	for (auto pairIterator = table.begin(); pairIterator != table.end(); pairIterator++)
	{
		auto vec = pairIterator->second;
		int sum = 0;
		for (auto it = vec->begin(); it != vec->end(); it++)
		{
			sum += *it;
		}

		sum *= pairIterator->first;
		max = MAX(max, sum);
		delete(vec);
	}

	return max;
}

// 使用单调栈
static int useMonotonousStack(const int* numbers, size_t size)
{
	stack<int> iStack;
	unordered_map<int, unordered_set<int>*> table;
	for (int i = 0; i < size; i++)
	{
		int cur = numbers[i];
		auto vec = new unordered_set<int>();
		vec->insert(cur);
		table.insert({ cur, vec });

		if (iStack.empty())
		{
			iStack.push(cur);
			continue;
		}

		while (!iStack.empty())
		{
			int top = iStack.top();
			if (top < cur)
			{
				break;
			}

			iStack.pop();
			// 退出栈的时候，top下面的元素需要记录top的数字，即与top相连并大于等于top的所有值
			auto topVec = table[top];
			if (!iStack.empty())
			{
				auto nextTop = iStack.top();
				auto nextTopVec = table[nextTop];
				for (auto it = topVec->begin(); it != topVec->end(); it++)
				{
					nextTopVec->insert(*it);
				}
			}

			auto curVec = table[cur];
			for (auto it = topVec->begin(); it != topVec->end(); it++)
			{
				curVec->insert(*it);
			}
		}

		iStack.push(cur);
	}

	while (!iStack.empty())
	{
		int top = iStack.top();
		iStack.pop();
		auto topVec = table[top];
		if (!iStack.empty())
		{
			auto nextTop = iStack.top();
			auto nextTopVec = table[nextTop];
			for (auto it = topVec->begin(); it != topVec->end(); it++)
			{
				nextTopVec->insert(*it);
			}
		}
	}

	int max = 0;
	for (auto pair = table.begin(); pair != table.end(); pair++)
	{
		//printf("%d:", pair->first);
		int sum = 0;
		for (auto it = pair->second->begin(); it != pair->second->end(); it++)
		{
			sum += pair->first * (*it);
			//printf("%d,", *it);
		}

		max = MAX(max, sum);
		delete(pair->second);
		//printf("\n");
	}

	return max;
}

//  定义: 数组中累积和与最小值的乘积, 假设叫做指标A。
//  给定一个数组，请返回子数组中, 指标A的最大的值。
// 
//  如 : [5, 3, 2, 1, 6, 7, 8, 4]
//  对于5, 要保证5是子数组中最小的数字, 有子数组[5], 累积和 : 5; 最小值乘积: 5 * 5 = 25
//  对于3, 要保证3是子数组中最小的数字, 有子数组[5, 3], [3], 累积和分别是 : 5 + 3, 3; 最小值乘积: (5 + 3) * 3 = 24, 3 * 3 = 9; 故应该取[5, 3]
//  对于2, 要保证2是子数组中最小的数字, 有子数组[5, 3, 2], [3, 2], [2], 累积和分别是: 5 + 3 + 2, 3 + 2, 2; 最小值乘积: (5 + 3 + 2) * 2 = 20, (3 + 2) * 2 = 10, 2 * 2 = 4; 故应该取[5, 3, 2]
//  对于1, 要保证1是子数组中最小的数字, 有子数组[5, 3, 2, 1], [3, 2, 1], [2, 1], [1], [1, 6],  [1, 6, 7], [1, 6, 7, 8], [1, 6, 7, 8, 4], [2, 1, 6]... 总之，应该取最长的[5, 3, 2, 1, 6,  7, 8, 4], 最小值乘积: (5 + 3 + 2 + 1 + 6 + 7 + 8 + 4) * 1 = 36
//  ...
//  对于6, 取[6, 7, 8], 最小值乘积 : (6 + 7 + 8) * 6 = 126
//  对于7, 取[7, 8], 最小值乘积 : (7 + 8) * 7 = 105
//  对于8, 取[8], 最小值乘积 : 8 * 8 = 64
//  对于4, 取[6, 7, 8, 4], 最小值乘积 : (6 + 7 + 8 + 4) * 4 = 100
// 
// 最终结果应该是126
int main_CumulativeSumAndMinProduct()
{
	int numbers[] = { 12,23,11,49,30,39,80,59 };
	size_t size = sizeof(numbers) / sizeof(int);
	int result = useLoop(numbers, size);
	printf("result1: %d\n", result);
	result = useMonotonousStack(numbers, size);
	printf("result2: %d\n", result);
	return 0;
}